using System;
using System.Collections.Generic;

public class PriorityQueueMin<T> where T : System.IComparable<T>
{
    private T[] heap;
    private int size;
    public PriorityQueueMin(int capacity)
    {
        if(capacity < 0) throw new ArgumentException("Capacity is less than 0");

        heap = new T[capacity];
        size = 0;
    }
    
    public int Size() =>size;
     public bool IsEmpty() =>size == 0;
     public T Peek(){
        if(IsEmpty())return default(T);
        return heap[0];
     }

     private int Parent(int index)=>(index - 1) / 2;
     private int Left(int index)=>2 * index + 1;
     private int Right(int index)=>2 * index + 2;

     public void Push(T value){

        if(size == heap.Length) Resize();
        heap[size] = value;

        Swim(size);
        size++;
     }

    public T Pop(){
        if(IsEmpty()) return default(T);
        T result = heap[0];
        heap[0] = heap[size - 1];

        heap[size - 1] = default(T);
        size--;

        Sink();
        return result;
    }

     /// <summary>
     /// 交换两个元素
     /// </summary>
     /// <param name="i"></param>
     /// <param name="j"></param>
     private void Swap(int i, int j){
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
     }

    /// <summary>
    /// 上浮 父子交换
    /// </summary>
    /// <param name="index"></param>
     private void Swim(int index){
        while(index>0){
            int parentIndex = Parent(index);
            if(heap[index].CompareTo(heap[parentIndex]) >= 0)break;
            Swap(index, parentIndex);

            //控制上浮条件
            index = parentIndex;
        }
     }

     /// <summary>
     /// 下沉 父子交换
     /// </summary>
     /// <param name="index"></param>
     private void Sink(){
        int index = 0;
        while(Left(index) < size){
            int childIndex = Left(index);
            if(childIndex + 1 < size //判断右节点是否存在
            //判断右子 < 左子 如果成立 则将childIndex 赋值为右子
            && heap[childIndex + 1].CompareTo(heap[childIndex]) < 0)childIndex++;

            if(heap[index].CompareTo(heap[childIndex]) <= 0)break;
            Swap(index, childIndex);

            //控制下沉条件
            index = childIndex;
        }
     }
    
    private void Resize(){
        T[] newHeap = new T[heap.Length * 2];
        System.Array.Copy(heap, 0, newHeap, 0, size);
        heap = newHeap;
    }
}
